package com.umgsai.wx.backend.test;

import com.alibaba.fastjson.JSON;

import java.util.List;

public class SearchMatrix {

    /*
    编写一个高效的算法来搜索mxn矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

    每行的元素从左到右升序排列。
    每列的元素从上到下升序排列。

    输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
    输出：true

    作者：力扣 (LeetCode)
    链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xmlwi1/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    */

    public static void main(String[] args) {
        String source = "[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]";
//        String source = "[[1],[3],[5]]";
//        String source = "[[1]]";
//        String source = "[[1,5,9,11,67]]";
        List<String> strings = JSON.parseArray(source, String.class);

        int[][] array = new int[strings.size()][JSON.parseArray(strings.get(0)).size()];

        int i = 0;
        for (String string : strings) {
            List<Integer> integers = JSON.parseArray(string, Integer.class);
            int j = 0;
            for (Integer integer : integers) {
                array[i][j] = integer;
                j++;
            }
            i++;
        }
        Boolean result = null;

        result = searchMatrix(array, -15);
        System.out.println(result);
        for (int[] ints : array) {
            for (int anInt : ints) {
                result = searchMatrix(array, anInt);
                System.out.println(result);
            }
        }
        result = searchMatrix(array, 180);
        System.out.println(result);


        System.out.println(searchMatrix(array, 29));
        System.out.println(searchMatrix(array, 25));
        System.out.println(searchMatrix(array, 20));
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        for (int[] ints : matrix) {
            boolean b = BinarySearch.binarySearch(ints, target);
            if (b) {
                return true;
            }
        }
        return false;
    }

    public static boolean searchMatrix1(int[][] matrix, int target) {
        int i = 0;
        int j = 0;

        int width = matrix[0].length;
        int height = matrix.length;

        if (matrix[i][j] > target) {
            return false;
        }
        while (true) {
            if (matrix[i][j] == target) {
                return true;
            }
            if (i == height - 1 && j == width - 1) {
                return false;
            }
            while (j < width - 1 && target > matrix[i][j]) {
                if (matrix[i][j] == target || target == matrix[i][j + 1]) {
                    return true;
                }
                if (target > matrix[i][j + 1]) {
                    j++;
                } else if (target < matrix[i][j + 1]) {
                    break;
                }
            }
            while (i < height - 1 && target > matrix[i][j]) {
                if (matrix[i][j] == target || target == matrix[i + 1][j]) {
                    return true;
                }
                if (target > matrix[i + 1][j]) {
                    i++;
                } else {
                    j--;
                }
            }
            if (i == height - 1 && j < width - 1 && target < matrix[i][j + 1]) {
                return false;
            }
        }
    }

}
